UVa/11556 - Switch bulbs/11556.cpp

   1 /*
   2   Problem: 11556 - Switch bulbs
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6   Not judged yet
   7  */
   8
   9 using namespace std;
  10 #include <algorithm>
  11 #include <iostream>
  12 #include <iterator>
  13 #include <sstream>
  14 #include <fstream>
  15 #include <cassert>
  16 #include <climits>
  17 #include <cstdlib>
  18 #include <cstring>
  19 #include <string>
  20 #include <cstdio>
  21 #include <vector>
  22 #include <cmath>
  23 #include <queue>
  24 #include <deque>
  25 #include <stack>
  26 #include <map>
  27 #include <set>
  28
  29 #define D(x) cout << #x " is " << x << endl
  30
  31 int d[1<<15], suiche[40];
  32
  33 int main(){
  34
  35   int T, caso = 1;
  36   scanf("%d", &T);
  37
  38   while (T--){
  39     int n, m;
  40     scanf("%d %d", &n, &m);
  41
  42     for (int i=0, k, x; i<m; ++i){
  43       suiche[i] = 0;
  44       scanf("%d", &k);
  45       while (k--){
  46         scanf("%d", &x);
  47         suiche[i] |= (1 << x);
  48       }
  49     }
  50
  51     for (int i=0; i<(1<<n); ++i) d[i] = INT_MAX;
  52     queue<int> q;
  53     d[0] = 0;
  54     q.push(0);
  55
  56     while (q.size()){
  57       int u = q.front(); q.pop();
  58       for (int k=0; k<m; ++k){
  59         int v = u ^ suiche[k]; //Toggles lights
  60         if (d[u] + 1 < d[v]){
  61           d[v] = d[u] + 1;
  62           q.push(v);
  63         }
  64       }
  65
  66     }
  67
  68     printf("Case %d:\n", caso++);
  69     int queries;
  70     scanf("%d", &queries);
  71     while (queries--){
  72       int destiny = 0;
  73       char buf[16];
  74       scanf("%s", buf);
  75       for (int i=n-1; i>=0; --i){
  76
  77         int bit = buf[i] - '0';
  78         destiny |= (bit << (n - i - 1));
  79       }
  80       printf("%d\n", d[destiny] < INT_MAX ? d[destiny] : -1);
  81     }
  82     printf("\n");
  83   }
  84   return 0;
  85 }